1. Field of the Invention
The present invention relates generally to a method for determining the stability of two dimensional polygonal scenes and, more particularly, to a kinematics based method for determining the stability of two dimensional polygonal scenes which designates each scene in a sequence of scenes as either stable or unstable.
2. Prior Art
Methods are known in the art for determining the stability of a collection of blocks. These methods differ from the one presented here in that these prior methods use an approach based on dynamics whereas the method presented herein is based on kinematics.
Kinematics is a branch of mechanics which deals with the motion of a physical system without reference to the forces which act on that system and without reference to the precise velocities and accelerations of the components of that system. A kinematic model takes the form of a set of constraints which specify the allowed combinations of positions of system components. The allowed motions follow from the possible transitions between allowed positions.
In contrast, dynamics is a branch of mechanics which deals with the motion of a physical system under the influence of forces applied to the components of that system. A dynamic model takes the form of a set of constraints which specify the relation between the positions of system components and the forces on those components. The motions follow by relating forces on system components to accelerations of those components and, in turn, to velocities and positions of those components.
Methods are also known in the art for determining the stability of a collection of line segments and circles. These methods differ from the one presented here in that they are based on a naive physical theory rather than on kinematics. Yet other methods are known in the art for determining the stability of a collection of line segments and circles. While these methods are based on kinematics, they have some fundamental flaws which lead them to produce incorrect results. Lastly, still another method is known in the art for determining the stability of a collection of rectangles. This method differs from the one presented herein in that it is based on a heuristic that does not always work.
Therefore it is an object of the present invention to provide a method for determining stability of two dimensional polygonal scenes which overcomes the problems of the prior art.
Accordingly, a method for determining the stability of a two dimensional polygonal scene is provided. Each polygon in the scene includes data representing a set L of line segments comprised of individual line segments l. The method determines whether the line segments are stable under an interpretation I. I is a quintuple (g, ⇄i, ⇄j, ⇄xcex8, ) and g is a property of line segments while ⇄i, ⇄j, ⇄xcex8, and  are relations between pairs of line segments. The method comprises the steps of: initializing a set Z of constraints to an empty set; for each l contained in L, if g(l), instantiating [{dot over (c)}(l)=0] and [{dot over (xcex8)}(l)=0] and adding them to Z; for each li, lj contained in L, if li⇄ilj, instantiating [{dot over (xcfx81)}(I(li, lj), li)=0] between li and lj and adding it to Z; for each li, lj contained in L, if li⇄jlj, instantiating [{dot over (xcfx81)}(I(li, lj), lj)=0] between li and lj and adding it to Z; for each li, lj contained in L, if li⇄xcex8lj, instantiating [{dot over (xcex8)}(li)={dot over (xcex8)}(lj)] between li and lj and adding it to Z; for each li, lj contained in L, if lilj, instantiating [{dot over (xcfx81)}(li)xc2x7"sgr"xe2x89xa6{dot over (l)}j(xcfx81(p(li),lj))xc2x7"sgr"] between li and lj and adding it to Z; instantiating [{dot over (E)}=xe2x88x921] between all l of L and adding it to Z; and determining the stability of the scene based upon whether Z has a feasible solution.
Also provided are a computer program product and program storage device for carrying out the method of the present invention and for storing a set of instructions to carry out the method of the present invention, respectively.